1. Field of the Invention
The present invention relates to a method of arranging and integrating a large number of logic cells in a semiconductor chip by using a computer.
2. Description of the Related Art
A gate array method (also called a master slice method) is known as a method of designing a semiconductor IC device. In this method, basic cells and input/output (I/O) cells each consisting of a predetermined number of transistors are regularly arranged on a master chip. Wiring between these gates (the basic cells and the I/O cells) is then performed in accordance with the specifications required by a user so as to design an LSI having a desired function.
A wafer on which only basic cells are arranged prior to a wiring step is generally called a master wafer. The process of performing wiring of a master wafer and allowing it to have a specific function as an LSI is called "personalizing".
In a gate array, inverters, NAND gates, flip-flops, and the like as cells can be freely realized by using a plurality of basic cells and performing wiring. All the wiring patterns (to be referred to as macrocells hereinafter) used as standard patterns are prepared in large quantities as a library. Efficient design can be performed by using this library.
FIG. 1 shows a master wafer chip as an example. Basic cells 3 are arranged within a chip 1 in the longitudinal and transverse directions without any gap. An I/O cell arrangement region 4 is formed along the periphery of the chip 1. I/O cells are arranged on the region 4. A user arranges a required number of macrocells of required types on array regions 2 of basic cells in accordance with the number of LSIs to be realized. Personalizing is then performed by wiring the terminals of the cells on the basis of circuit connection data.
Arrangement/wiring processing for a high-integration, large-scale gate array is difficult to perform by means of manual design. For this reason, automatic arrangement/wiring processing using a computer is normally performed. Automatic arrangement processing for determining the position of each macrocell on a chip is roughly divided into two steps: the step of determining the initial position of each logic cell (the initial arrangement step); and the step of improving a given initial arrangement result (the arrangement improving step). As to the arrangement improving step, several methods have been proposed. One of the following three factors is generally used as an objective function of the algorithm of such a method:
(a) the minimum ratio of wiring lengths;
(b) the minimum ratio of the number of wirings through via holes; and
(c) a uniform wiring density level.
As a method using the factor (a), an FDR method is available (reference: Hanan, M., Wolff, P.K. and Anguli, B.J., "Some Experimental Results on Placement Techniques", Proc. 13th Design Automation Conference, pp. 214-224, 1976).
In the FDR method, the connecting relationship between cells is expressed as a tension between the cells. The overall wiring length is minimized by interchanging cells or moving cells so as to reduce this tension.
As a method using the factor (b), a MIN-CUT method is available (reference: M.A. Breuer, "MIN-CUT Placement", Proc. Journal of Design Automation and Fault-Tolerant Computing, October, pp. 343-362, 1977).
In the MIN-CUT method, the interchange of cells is performed to decrease the number of signal lines (to be referred to as a cut number hereinafter) extending across imaginary cutlines of a chip region, thus minimizing the total cut number.
In either of the methods using the factors (a) and (b), wiring requests tend to locally concentrate on a chip, resulting in an inadequate arrangement of a gate array. This makes wiring difficult.
In automatic arrangement/wiring processing for a gate array, it is strongly required to wire all the cells without wiring errors and short-circuiting. Methods using the factor (c) aim at a wiring rate of 100%. For example, a MAX-CUT MIN method is available (reference: H. Shiraishi, F. Hirose, "Efficient Placement and Routing Techniques for Master Slice LSI", Proc. 17th Design Automation Conference, pp. 458-464, 1980).
In the MAX-CUT MIN method, the cut number of a cutline having the maximum cut number is decreased. In this method, although the wiring request of each cutline can be restricted to a value less than a permitted value, wiring of a finer pattern is difficult to achieve. For this reason, the wiring rate could not be sufficiently increased. In the above-described method, since a specific wiring model (to be referred to as a net model hereinafter) is used to estimate an imaginary wiring route, the wiring result is greatly changed depending on a net model to be used. The selection of such a net model greatly influences the performance of automatic arrangement and hence is important. However, with an increase in accuracy of a net model, the processing time is increased and the processing becomes complicated.
As a method of solving these problems, a method of distributing connecting pins on a chip at a uniform density level is available (reference: U. Schulz, Rainer Zuhlke, "A Study on Bipolar VLSI Gate-Arrays Assuming Four Layers of Metal", Proc. IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. SC-17, No. 3, pp. 427-480, 1982). Since a strong correlation is present between a wiring distribution and a connection pin distribution, a uniform distribution of wiring requests on a chip is substantially equivalent to a uniform distribution of connection pins. However, wiring cannot be satisfactorily facilitated by simply performing uniform distribution of the connection pins. This is because factors which weaken the correlation between a wiring distribution and a connection pin distribution are present. For example, actual cells include portions which cannot be used for wiring (to be referred to as inhibited areas for wiring hereinafter) and cells vary in size. FIGS. 2A and 2B show states wherein the same number of connection pins (connection pins 9) are respectively included in lattices having the same area (defined by vertical and horizontal lattice sides 5 and 6). Reference numeral 10 denotes an inhibited area for wiring; and 12, a cell. In comparison with FIG. 2A, it is apparent from the sizes of wiring regions that the wiring in FIG. 2B can be more easily performed under the same wiring conditions. As described above, even with the same distribution of connection pins, the difficulty of wiring may vary. For these reasons, in the above-described method, wiring could not be satisfactorily facilitated. In the above-described method, therefore, the connection pins 9 and the prohibition regions are difficult to process independently in order to facilitate wiring.
As described above, in the method of minimizing the wiring length or the number of wirings through via holes, complicated processing is required, and local concentration of wirings is caused to interfere with an increase in wiring rate. In the method of uniforming the distribution of wirings, the processing time is increased and the processing becomes complicated. Furthermore, in the method of uniforming the distribution of connection pins on a chip, the effect of decreasing the wiring density level is insufficient.
As another method of improving an arrangement, a pairwise interchange method and a neighborhood interchange method are available. These methods are disclosed in M. Haman and J.M. Kurtzberg, "Placement Techniques", Chaps. 5 in Design Automation of Digital Systems: Theory and Techniques, Vol. 1 (ed. M.A. Breuer) Prentice Hall N.J. 1972, pp. 213-282. In either of the methods, logic cells are interchanged with each other in a layout region by a given method so as to satisfy each objective function.
The problem of such a method is that it takes a long period of time to obtain a global optimal solution. In order to solve the problem of a long processing time, hierarchical processing may be considered. In this hierarchical processing, the size of a layout region to be processed at once is limited to a given value. In this processing, however, a problem is still left unsolved when a global optimal solution is to be obtained as the final object of arrangement improving processing. In this processing, in order to increase the processing time, orthogonal imaginary lines are set in layout regions (regions divided by these imaginary lines will be called lattices hereinafter). However, the initially-set lattice size greatly influences an arrangement result.
In addition, whether to move or interchange logic cells between lattices is determined under the limitation that overlapping of cells within a lattice is not allowed. This limitation greatly interferes with an improvement in arrangement. This is a factor which largely reduces the degree of freedom of improvement in a gate array in which positions allowing arrangement of logic cells are limited.